// 给你一个字符串 s，找到 s 中最长的回文子串。

// 示例 1：

// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案。
public class Solution{
    public String longestPalindrome(String s){
        int len = s.length();
        if(len<2)
        {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        boolean[][] dp =new boolean[len][len];
        char[] c = s.toCharArray();
        for(int i =0;i<len;i++)
        {
            dp[i][i] = true;
        }
        for(int j=1;j<len;j++)
            for(int i=0;i<j;i++){
                if(c[i]!=c[j])
                {
                    dp[i][j] = false;
                }
                else{
                    if(j-i<3)
                    {
                        dp[i][j]=true;
                    }
                    else{
                        if(dp[i+1][j-1]==true)
                            dp[i][j]=true;
                        else
                            dp[i][j]=false;
                    }
                }
                if(dp[i][j]==true&&j-i+1>maxLen)
                {
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        return s.substring(begin,begin+maxLen);
    }
}